package cg.studio.algorithm.permutation;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * TODO: the string result list is order-less.
 * how to make them order-able
 * 
 * Generate permutation by insert char into generate string
 * for example, chars: abc
 *   - order-less:  a ---insert b---> ab, ba --insert c--> abc, acb, cab; bac, bca, cba
 *   - order:       
 * @author Bright Chen
 *
 */
public class InsertionPermutator implements Permutator
{

  public List< char[] > permutate( String str )
  {
    if( str ==  null || str.length() == 0 )
      return Collections.emptyList();
    str = str.toUpperCase();
    
    final char[] chars = str.toCharArray();
    
    // a list of char[], each char[] is a permutation
    List< char[] > results = new ArrayList< char[] >();
    
    //the initial result
    char[] aResult = new char[ chars.length ];
    aResult[0] = chars[0];
    results.add( aResult );
    
    for( int insertingCharIndex = 1; insertingCharIndex < chars.length; ++insertingCharIndex )
    {
      //the char which get from the original str and going to insert into the results
      char insertingChar = chars[ insertingCharIndex ];
      
      // insert this char into the each result
      final int originalResultSize = results.size();
      for( int resultIndex = 0; resultIndex < originalResultSize; ++resultIndex )
      {
        char[] theResult = results.get( resultIndex );
        //the size of result before inserting
        int theResultSize = insertingCharIndex;
        //insert into tail first, this can save a copy
        theResult[ theResultSize ] = insertingChar;
        for( int insertedToIndex = theResultSize-1; insertedToIndex >= 0 ; --insertedToIndex )
        {
          //if the insertingChar same as a char or several continuous same chars, insert inserting at the tail.
          //so, if the char at insertedToIndex same as insertingChar, ignore this loop
          if( theResult[ insertedToIndex ] == insertingChar )
            continue;
          
          char[] copiedResult = copyChars( chars.length, theResult, theResultSize, insertedToIndex );
          copiedResult[ insertedToIndex ] = insertingChar;
          
          //add to the list
          results.add( copiedResult );
        }
        
      }
    }    

    return results;
  }

  
  /**
   * create an array of char, which capacity is <capacity>,
   * and copy data from <original>[ 0, <emptyIndex> ), 
   * and leave the value of <emptyIndex> to empty, and right shift the value after emptyIndex;
   * 
   * @param capacity the capacity of the array which will be created
   * @param original the original char array
   * @param size the size of the original array
   * @param emptyIndex the index of the created array which will be leave as empty
   * 
   * @return the created char array
   */
  protected char[] copyChars( int capacity, char[] original, int size, int emptyIndex )
  {
    char[] chars = new char[ capacity ];
    
    for( int index = 0; index < emptyIndex; ++index )
    {
      chars[ index ] = original[ index ];
    }
    for( int index = emptyIndex+1; index <= size; ++index )
    {
      chars[ index ] = original[ index-1 ];
    }
    return chars;
  }
}
